package br.edu.unifei.mestrado.fm;

import java.util.Date;
import java.util.Iterator;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import br.edu.unifei.mestrado.commons.graph.GraphWrapper;
import br.edu.unifei.mestrado.commons.graph.RelationshipWrapper;
import br.edu.unifei.mestrado.commons.partition.AbstractPartitionIndex;
import br.edu.unifei.mestrado.commons.partition.BestPartition;

public abstract class FM {

	private Logger logger = LoggerFactory.getLogger(this.getClass());

	private static int Smax = 0;

	//TODO: corrigir esses sizes!!!!!!!!!!!!!!!!!1
	private int sizeA = 0;
	private int sizeB = 0;
	
	public void readGraph() {
		getGrafo().readGraph();
	}

	/**
	 * Recupera o objeto grafo especializado.
	 * 
	 * @return
	 */
	protected abstract GraphWrapper getGrafo();

	public abstract AbstractPartitionIndex getPartitionIndex();

	
	private int balanceConstraint() {
		double R = 0.5;
		int V = sizeA + sizeB;

		double F1 = R * V - FM.Smax;
		double F2 = R * V + FM.Smax;
		if (F1 < V && V < F2) {
			return 1;
		} else {
			return 0;
		}
	}

	private void fillArrays(NetList netList, CellList cellList) {
		boolean newNet = false;
		FM.Smax = 0;
		for (RelationshipWrapper aresta : getGrafo().getAllEdges()) {
			aresta.getStartNode().lock();
			aresta.getEndNode().lock();

			long id1 = aresta.getStartNode().getId();
			long id2 = aresta.getEndNode().getId();
			newNet = false;
			
			// preencher as 2 estruturas de dados

			Cell cell1 = cellList.getCellById(id1);
			if (cell1 == null) {
				newNet = true;
				cell1 = cellList.createCell(id1);
			}

			Cell cell2 = cellList.getCellById(id2);
			if (cell2 == null) {
				newNet = true;
				cell2 = cellList.createCell(id2);
			}
			if (newNet) {
				Net net = netList.createNet(cell1, cell2);
				// imprimeNetArray(netArray, netArraySize);

				cell1.getNets().insert(net);
				if (cell1.getNets().size() > FM.Smax) {
					FM.Smax = cell1.getNets().size();
				}
				cell2.getNets().insert(net);
				if (cell2.getNets().size() > FM.Smax) {
					FM.Smax = cell2.getNets().size();
				}
				// imprimeCellArray(cellArray, cellArraySize);
			}
		}

		cellList.imprimeCellArray();
		netList.imprimeLista();
	}

	private void calculoGanhoInicial(Bucket bucketA, Bucket bucketB, NetList netList, CellList cellList) {

		for (Cell cell : cellList) {
			int oldGain = cell.getGain();

			Block fromBlock = cell.getFromBlock();
			Block toBlock = cell.getToBlock();

			cell.updateGain(fromBlock, toBlock);
			if (cell.getPartition() == 1) { // a celula esta na particao 1
				bucketA.updateGainForNode(cell.getGain(), oldGain, cell);
			} else {
				bucketB.updateGainForNode(cell.getGain(), oldGain, cell);
			}
			bucketA.print("Bucket A:");
			bucketB.print("Bucket B:");
		}
	}

	private void updateGanho(Cell baseCell, Bucket bucketA, Bucket bucketB, CellList cellList) {
		Block fromBlock = baseCell.getFromBlock();
		Block toBlock = baseCell.getToBlock();

		NetList nets = baseCell.getNets();
		for (Net net : nets) {
			for (Cell cell : cellList) {

				if (!cell.isLocked()) {
					if (fromBlock.getSizeOf(net) == 1) {
						cell.incrementGain();
					} else if (toBlock.getSizeOf(net) == 0) {
						cell.decrementGain();
					}
					// atualiza os ganhos para refletir o movimento da celula
					fromBlock.decrement(net);
					toBlock.increment(net);
					// verifica redes criticas antes de mover
					if (fromBlock.getSizeOf(net) == 0) {
						cell.decrementGain();
					} else if (fromBlock.getSizeOf(net) == 1) {
						cell.incrementGain();
					}
					int oldGain = cell.getGain();
					if (oldGain != cell.getGain()) {
						if (cell.getPartition() == 1) { // a celula esta na particao 1
							bucketA.updateGainForNode(cell.getGain(), oldGain, cell);
						} else {
							bucketB.updateGainForNode(cell.getGain(), oldGain, cell);
						}
					}
				}
			}
		}
	}

	/**
	 * only cells that contain the maximum gain AND also do not violate the balance constraint can be chosen
	 * as the base cell.
	 * 
	 * TODO: Mas o que fazer se a célula com maximo ganho violar a restrição de balenceamento???
	 */
	private Cell chooseBaseCell(Bucket bucketA, Bucket bucketB) {

		Iterator<Cell> maxGainListA = bucketA.getVerticesWithMaxGain().iterator();
		Iterator<Cell> minGainListA = bucketA.getVerticesWithMinGain().iterator();

		Iterator<Cell> maxGainListB = bucketB.getVerticesWithMaxGain().iterator();
		Iterator<Cell> minGainListB = bucketB.getVerticesWithMinGain().iterator();

		Cell cell = null;
		while (true) {

			if (maxGainListA.hasNext()) {// maior ganho positivo para bucket A
				cell = maxGainListA.next();
				int balanced = balanceConstraint();
				if (balanced == 1) {
					bucketA.removeNodeWithGain(cell.getGain(), cell);
					break;
				}
			} else if (maxGainListB.hasNext()) {// maior ganho positivo para bucket B
				cell = maxGainListB.next();
				int balanced = balanceConstraint();
				if (balanced == 1) {
					bucketB.removeNodeWithGain(cell.getGain(), cell);
					break;
				}
			} else if (minGainListA.hasNext()) {// maior ganho negativo para bucket A
				cell = minGainListA.next();
				int balanced = balanceConstraint();
				if (balanced == 1) {
					bucketA.removeNodeWithGain(cell.getGain(), cell);
					break;
				}
			} else if (minGainListB.hasNext()) {// maior ganho negativo para bucket B
				cell = minGainListB.next();
				int balanced = balanceConstraint();
				if (balanced == 1) {
					bucketB.removeNodeWithGain(cell.getGain(), cell);
					break;
				}
			} else {
				break;
			}
		}
		if (cell != null) {
			logger.info("Celula escolhida: " + cell.getId() + " gain: " + cell.getGain());
		} else {
			logger.info("Nenhuma celula encontrada.\n");
		}
		return cell;
	}

	private void exchangePairs(CellList selected, int qtd) {
		for (Cell cell : selected) {
			logger.info("Exchanging node " + cell.getId() + " gain: " + cell.getGain());
			if (cell.getPartition() == 1) {
				cell.setPartition(2);
			} else {
				cell.setPartition(1);
			}
		}
	}

	public BestPartition executeFM() {
		
		/**
		 * 1. Gather input data and store into the relevant structures. <br>
		 * 2. Compute gains of all cells <br>
		 * 3. i = 1, Select base cell ci that has <br>
		 * (i) max. gain, <br>
		 * (ii) satisfies balance criterion. If tie, Then use size criterion or internal connections. If no
		 * base cell, then EXIT; <br>
		 * 4. Lock ci; update gains of cells of affected critical nets <br>
		 * 5. If free cell is not-empty, Then i = i+1; select next base cell and go to step 3. <br>
		 * 6. Select best sequence of moves c1, c2, ..., ck; (1<=k <= i) such that G(k) = is maximum. If tie,
		 * then choose subset that achieves a superior performance. If G <= 0, Then EXIT <br>
		 * 7. Make all i moves permanent; Free all cells; Goto step 1.
		 */
		
		NetList netList = new NetList();
		CellList cellList = new CellList();

		Bucket bucketA = new Bucket();
		Bucket bucketB = new Bucket();
		CellList selected = new CellList();

		fillArrays(netList, cellList);

		cellList.getInitialArbitraryPartition(getGrafo().getSizeNodes());

		calculoGanhoInicial(bucketA, bucketB, netList, cellList);

		Cell cell = chooseBaseCell(bucketA, bucketB);
		while (cell != null) {

			cell.lock();
			updateGanho(cell, bucketA, bucketB, cellList);
			selected.insert(cell);

			cell = chooseBaseCell(bucketA, bucketB);
		}

		int k = calculateKMoves(selected);
		if (k > 0) {
			exchangePairs(selected, k);
		}
		cellList.printPartitions();
		logger.info("End of partitioning:");

		return new BestPartition(-1);//TODO: criar o best partition corretamente.
	}

	/**
	 * Calcula quantos elementos realmente serão movidos
	 * @param selected
	 * @return
	 */
	private int calculateKMoves(CellList selected) {
		int k = 0;
		int k_tmp = 0;
		int G = 0;
		int G_tmp = 0;
		for (Cell cellSelected : selected) {
			G_tmp += cellSelected.getGain();
			k_tmp++;
			if (G_tmp > G) {
				k += k_tmp;
				G += G_tmp;

				G_tmp = 0;
				k_tmp = 0;
			}
		}
		return k;
	}
	
	public void execute() {
		try {
			getGrafo().beginTransaction();
			readGraph();
			getGrafo().endTransaction();
		} finally {
			getGrafo().finish();
		}

		try {
			long time = System.currentTimeMillis();
			BestPartition result = executeFM();

			time = System.currentTimeMillis() - time;
			logger.warn("Fim do FM. Tempo gasto: " + time + " ms File: " + getGrafo().getGraphFileName()
					+ " - Hora Termino: " + new Date());
			result.printSets();
		} catch (Throwable e) {
			logger.error("Erro executando KL.", e);
		} finally {
			getGrafo().finish();
		}
	}
}
